package sort;

/**
 * 归并排序
 */
public class MergeSort {


    public static void merge(int[] a,int start,int mid,int end){
        int[] tmp = new int[end-start+1];

        int i = start;
        int j = mid+1;
        int k = 0;
        while(i<=mid&&j<=end){
            if(a[i]<=a[j])
                tmp[k++] = a[i++];
            else{
                tmp[k++] = a[j++];
            }
        }

        //合并剩下的值
        while(i<=mid)
            tmp[k++] = a[i++];
        while(j<=end)
            tmp[k++] = a[j++];


        for(i = 0;i<k;i++)
            a[start+i] = tmp[i];
        tmp = null;
    }

    public static void mergeSortUp2Down(int[] a,int start,int end){
        if(a==null||start>=end)
            return;
        int mid = (end + start)/2;
        mergeSortUp2Down(a,start,mid);
        mergeSortUp2Down(a,mid+1,end);
        merge(a,start,mid,end);
    }

    public static void main(String[] args) {
        int i;
        int a[] = {80,30,60,40,20,10,50,70};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        mergeSortUp2Down(a, 0, a.length-1);        // 归并排序(从上往下)

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}
